#ifndef GAMEENGINE_CORE_GRAPH_OCTREE_HPP
#define GAMEENGINE_CORE_GRAPH_OCTREE_HPP

#ifdef GAMEENGINE_NAMESPACES
namespace GameEngine {
#endif


//=====================================================================


//! Default constructor
/*!
 @param max_depth The maximum depth allowed for the octree structure
 */
template <class E, class T>
Octree<E,T>::Octree(int max_depth) {
	subdivide(node_, max_depth);
}

//! Constructor
/*!
 @param box The box associated to the whole octree
 @param max_depth The maximum depth allowed for the octree structure
 */
template <class E, class T>
Octree<E,T>::Octree(const Box3d<T>& box, int max_depth) : node_(box) {
	subdivide(node_, max_depth);
}

//! Copy constructor
/*!
 @param rhs The octree to copy
 */
template <class E, class T>
Octree<E,T>::Octree(const Octree& rhs) : node_(rhs.node_), elements_(rhs.elements_) {}

//! Destructor
template <class E, class T>
Octree<E,T>::~Octree() {}

//! Assignment operator
/*!
 @param rhs The octree to copy
 */
template <class E, class T>
Octree<E,T>& Octree<E,T>::operator=(const Octree& rhs) {
	if ( &rhs != this ) {
		node_ = rhs.node_;
		elements_ = rhs.elements_;
	}
	return *this;
}

//! Accessor to the elements of the octree (read only)
/*!
 @return A constant reference to the elements of the octree
 */
template <class E, class T>
const std::vector<E>& Octree<E,T>::elements() const {
	return elements_;
}

//! Accessor to the elements of the octree (read-write)
/*!
 @return A reference to the elements of the octree
 */
template <class E, class T>
std::vector<E>& Octree<E,T>::elements() {
	return elements_;
}

//! Try to add the element to the octree
/*!
 @param element The element to add
 @param location The location associated to the element
 @param unique If set to true, forbids the element to be added multiple times to the octree
 @return True if the element could be added to this octree, false otherwise. An element may
         not be added if its location does not fit with the box of the main octree node.
 */
template <class E, class T>
bool Octree<E,T>::add_element(const E& element, const Point3d<T>& location, bool unique) {
	// Check the location
	if ( node_.box().inside(location) == false ) return false;

	// Check uniqueness
	if ( unique == true ) {
		if ( find_element(element) == true ) return false;
	}

	// Add the element
	elements_.push_back(element);
	node_.add_element((OctreeIndex)((int)elements_.size()-1), location, false);
	return true;
}

//! Try to add the element to the octree
/*!
 @param element The element to add
 @param location The location associated to the element
 @param unique If set to true, forbids the element to be added multiple times to the octree
 @return True if the element could be added to this octree, false otherwise. An element may
         not be added if its location does not fit with the box of the main octree node.
 */
template <class E, class T>
bool Octree<E,T>::add_element(const E& element, const Box3d<T>& location, bool unique) {
	// Check the location
	if ( node_.box().overlap(location) == false ) return false;

	// Check uniqueness
	if ( unique == true ) {
		if ( find_element(element) == true ) return false;
	}

	// Add the element
	elements_.push_back(element);
	node_.add_element((OctreeIndex)((int)elements_.size()-1), location);
	return true;
}

//! Try to remove the element from this octree
/*!
 @param element The element to remove
 @return The number of elements that were removed from the octree
 @note This function is quite slow and should be called as little as possible. Future versions
       of GameEngine are expected to increase the speed of this function.
 */
template <class E, class T>
typename Octree<E,T>::ElementCount Octree<E,T>::remove_element(const E& element) {
	ElementCount res = 0;

	// Look for the elements of this octree node
	OctreeIndex index = 0;
	int count = (int)elements_.size(), cur_count = 0;
	for ( std::vector<E>::iterator it = elements_.begin(); it != elements_.end(); ++it ) {
		++cur_count;
		// Iterate over the elements of the octree
		if ( *it == element ) {
			// Remove the associated index in the octree node of the octree
			// Iterate over the non-empty nodes of the octree
			for ( Node::Iterator itr(node_, OctreeNodeItr::NonEmptyNodes); itr.more(); itr.next() ) {
				// Iterate over the elements of this octree node
				std::vector<OctreeIndex>& elements = itr.cur().elements();
				int count2 = (int)elements.size(), cur_count2 = 0;
				for ( std::vector<OctreeIndex>::iterator ite = elements.begin(); ite != itr.cur().elements().end(); ++ite ) {
					++cur_count2;

					// Nothing to do if index is below index to remove
					if ( *ite < index ) continue;

					// If this is the index to remove, remove it
					if ( *ite == index ) {
						elements.erase(ite);
						if ( cur_count2 == count2 ) break;
						continue;
					}

					// If index is greater than the index to remove, decrease it
					--(*ite);
				}
			}

			// Remove the element from the octree
			elements_.erase(it);
			++res;
			if ( cur_count == count ) break;
		}
		++index;
	}

	// Return the result
	return res;
}

//! Try to find the element in this octree
/*!
 @param element The element to find
 @return True if element could be found, false otherwise
 */
template <class E, class T>
bool Octree<E,T>::find_element(const E& element) const {
	// Look for the elements of this octree node
	for ( std::vector<E>::const_iterator it = elements_.begin(); it != elements_.end(); ++it ) {
		if ( *it != element ) continue;
		return true;
	}

	// Return the result
	return false;
}

//! Try to simplify the octree by removing all nodes whose number of elements is below given number
/*!
 @param nb_elements The threshold for the number of elements to keep the octree node
 */
template <class E, class T>
bool Octree<E,T>::simplify(ElementCount nb_elements) {
	return simplify(node_, nb_elements);
}

//! Try to simplify the octree node by removing all children nodes whose number of elements is below given number
/*!
 @param node The octree node to simplify
 @param nb_elements The threshold for the number of elements to keep the octree node
 */
template <class E, class T>
bool Octree<E,T>::simplify(Node& node, ElementCount nb_elements) {
	// Check if node can be simplified
	Node* children = node.children();
	if ( children == nil ) return true;

	// Check the number of elements
	if ( node.nb_elements() < nb_elements ) {
		node.merge(false);
		return true;
	}

	// Recursively test the children
	bool res = true;
	for ( int k = 0; k < 8; ++k ) {
		res &= simplify(children[k], nb_elements);
	}
	return res;
}

//! Recursively subdivide the octree node until given recursion level has been reached
/*!
 @param node The node to subdivide
 @param level The depth of the octree below this node
 @return True if node could be subdivided at the recursion level, false otherwise
 */
template <class E, class T>
bool Octree<E,T>::subdivide(Node& node, int level) {
	// Finished the recursion
	if ( level <= 0 ) return true;

	// Subdivide the node
	if ( node.subdivide() == false ) return false;

	// Subdivide the descendants
	Node* children = node.children();
	bool res = true;
	for ( int k = 0; k < 8; ++k ) {
		res &= subdivide(children[k],level-1);
	}

	// Return the result
	return res;
}

//! Get the low-level octree node that covers the given location
/*!
 @param location The location that should be queried
 @return A pointer to the low-level octree node that covers the given location (may
         be nil if the location does not fit the box of this node)
 */
template <class E, class T>
typename const Octree<E,T>::Node* Octree<E,T>::get_node(const Point3d<T>& location) const {
	return node_.get_node(location);
}

//! Get the low-level octree node that covers the given location
/*!
 @param location The location that should be queried
 @return A pointer to the low-level octree node that covers the given location (may
         be nil if the location does not fit the box of this node)
 */
template <class E, class T>
typename Octree<E,T>::Node* Octree<E,T>::get_node(const Point3d<T>& location) {
	return node_.get_node(location);
}

//! Get the octree nodes that cover the given location
/*!
 @param location The location that should be queried
 @param type The type of nodes to be considered
 @return A pointer to the low-level octree node that covers the given location (may
         be nil if the location does not fit the box of this node)
 */
template <class E, class T>
std::list< typename const Octree<E,T>::Node* > Octree<E,T>::get_nodes(const Box3d<T>& location, OctreeNodeItr::OctreeNodeItrType type) const {
	return node_.get_nodes(location, type);
}

//! Get the octree nodes that cover the given location
/*!
 @param location The location that should be queried
 @param type The type of nodes to be considered
 @return A pointer to the low-level octree node that covers the given location (may
         be nil if the location does not fit the box of this node)
 */
template <class E, class T>
std::list< typename Octree<E,T>::Node* > Octree<E,T>::get_nodes(const Box3d<T>& location, OctreeNodeItr::OctreeNodeItrType type) {
	return node_.get_nodes(location, type);
}


//=====================================================================


#ifdef GAMEENGINE_NAMESPACES
} // namespace GameEngine
#endif

#endif
